import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/22
 * \* Time: 12:27
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class K个一组翻转链表 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /** 反转区间 [a, b) 的元素，注意是左闭右开 */
    ListNode reverse(ListNode a,ListNode b){
        ListNode pre,cur,nxt;
        pre=null;
        cur=a;
        nxt=b;
        while (cur!=b){
            nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }

    ListNode reverseKGroup(ListNode head, int k){
        if(head==null){
            return null;
        }
        ListNode a, b;
        a = b = head;
        // 不足 k 个，不需要反转，base case
        for(int i=0;i<k;i++){
            if(b==null){
                return head;
            }
            b=b.next;
        }
        // 反转前 k 个元素
        ListNode newHead=reverse(a,b);
        // 递归反转后续链表并连接起来
        a.next=reverseKGroup(b,k);
        return newHead;
    }
}